package LeetCode.exercise;

import java.util.LinkedList;
import java.util.Queue;

public class LC1926 {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;
    boolean[][] flag;
    public int nearestExit(char[][] maze, int[] entrance) {
        Queue<int[]> q = new LinkedList<>();
        m = maze.length;
        n = maze[0].length;
        flag = new boolean[m][n];
        q.offer(entrance);
        int res = 0;
        while(!q.isEmpty()){
            int size = q.size();
            res++;
            while(size-- > 0){
                int[] tmp = q.poll();
                int a = tmp[0], b = tmp[1];
                flag[a][b] = true;
                for(int i = 0; i < 4; i++){
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !flag[x][y]){
                        q.offer(new int[]{x, y});
                        flag[x][y] = true;
                        if((x == 0 || x == m-1 || y == 0 || y == n-1) && maze[x][y] == '.'){
                            return res;
                        }
                    }
                }
            }
        }
        return -1;
    }
}
